package leetcode.templates.merge;

// 窗口不回退
// 327. 区间和的个数
public class MaxMerge {

	private long array[];

	public MaxMerge(long[] array) {
		this.array = array;
	}

	public int process(int L, int R) {
		if (L == R) {
			int ans = 0;
//			ans = array[L] >= lower && array[L] <= upper ? 1 : 0;
			return ans;
		}
		int M = L + ((R - L) >> 1);
		return process(L, M) + process(M + 1, R) + merge(L, M, R);
	}

	public int merge(int L, int M, int R) {
		int ans = 0;
//		int l = L, r = L;
//		for (int i = M + 1; i <= R; i++) {
//			long sum = array[i];
//			long min = sum - upper, max = sum - lower;
//			while (r <= M && array[r] <= max) {
//				r++;
//			}
//			while (l <= M && array[l] < min) {
//				l++;
//			}
//			ans += r - l;
//		}
		long[] help = new long[R - L + 1];
		int p = 0;
		int p1 = L, p2 = M + 1;
		while (p1 <= M && p2 <= R) {
			help[p++] = array[p1] <= array[p2] ? array[p1++] : array[p2++];
		}
		while (p1 <= M) {
			help[p++] = array[p1++];
		}
		while (p2 <= R) {
			help[p++] = array[p2++];
		}
		for (p = 0; p < help.length; p++) {
			array[L + p] = help[p];
		}
		return ans;
	}
}
